#include <iostream>

using namespace std;

int main(int argc, char* argv[])
{
	long t, a, b, idx = 0;
	int* result;
	cin>>t;
	if (cin.fail()) {
		return 1;
	} else if (t < 0 || t > 10000) {
		return 1;
	} else {
		result = new int[t];
		for (int i = 0; i < t; i++) {
			cin>>a>>b;
			if (cin.fail()) {
				return 1;
			}
			if (a < 0 || b < 0) {
				return 1;
			}
			int remainder = a, remainder1 = 1;
			while (b > 1) {
				if (b % 2 == 1) {
					remainder1 = (remainder * remainder1) % 9907;
				}
				b = b / 2;
				remainder = (remainder * remainder) % 9907;
			}
			result[idx++] = (remainder * remainder1) % 9907;
		}
		for (int i = 0; i < idx; i++) {
			cout<<result[i]<<endl;
		}
		delete[] result;
	}
	return 0;
}